1. The Field of the Invention
The present invention relates to novel systems and methods for authenticating independent, executable software entities operating within a computer system. More particularly, the present invention relates to the use of modular components for inclusion within independent, executable entities to dynamically authenticate the independent, executable entities to each other.
2. The Relevant Technology
Encryption is a technology dating from ancient times. In modern times, encryption of military communications has been common. However, since the famous xe2x80x9cENIGMAxe2x80x9d machine of World War II, cryptography has been used in numerous functions. One of those functions is special purpose software or applications that may be hosted on computers. Hiding underlying algorithms, limiting access, inhibiting reverse engineering, limiting unauthorized use, controlling licensor, and the like may be legitimate uses of cryptography.
Modem cryptography protects data transmitted over high-speed electronic lines or stored in computer systems. There are two principal objectives: secrecy, to prevent the unauthorized disclosure of data, and integrity (or authenticity), to prevent the unauthorized modification of data. The process of disguising plaintext data in such a way as to hide its substance is encryption, and the encrypted result is cyphertext. The process of turning cyphertext back into plaintext is decryption.
A cryptographic algorithm, also called a cipher, is the computational function used to perform encryption and/or decryption. Both encryption and decryption are controlled by a cryptographic key or keys. In modern cryptography, all of the security of cryptographic algorithms is based in the key or keys and does not primarily depend on keeping any details of the algorithms secret.
There are two general types of key-based cryptographic algorithms: symmetric and public-key. Symmetric algorithms (also called secret-key algorithms) are algorithms where the encryption key can be calculated from the decryption key and vice versa (and in fact these keys are usually the same). These require that a sender and receiver agree on these keys before they can protect their communications using encryption. The security of these algorithms rests in the key, and divulging the key allows anyone to encrypt and decrypt data or messages with it.
In public-key algorithms (also called asymmetric algorithms), the keys used for encryption and decryption differ from each other in such a way that at least one key is computationally infeasible to determine from the other. To ensure secrecy of data or communications, only the encryption key need be kept private, and the encryption key can thus be made public without danger of encrypted data being decipherable by anyone other than the holder of the private decryption key. Conversely, to ensure integrity of data or communications, only the encryption key need be kept private, and a holder of a publicly-exposed decryption key can be assured that any ciphertext that decrypts into meaningful plaintext using this key could only have been encrypted by the holder of the corresponding private key, thus precluding any tampering or corruption of the ciphertext after its encryption.
Most public-key cryptographic algorithms can be used to provide only one of secrecy or integrity but not the other; some algorithms can provide either one but not both. The RSA (Rivest, Shamir, and Adleman) public-key algorithm (U.S. Pat. No. 4,405,829), however, whose security is based on the difficulty of factoring large numbers, has been effective in providing both secrecy and integrity.
A private key and a public key may be thought of as functionally reciprocal. Thus, whatever a possessor of one key of a key pair can do, a possessor of the other key of the key pair can undo. The result is that pairwise, secret, protected communication may be available without an exchange of keys. Thus, in general, a receiver, in possession of its own private key may decrypt messages targeted to the receiver and encrypted by the sender using the receiver""s public key. A receiver may authenticate a message, using its own copy of a sender""s public key, to decrypt data (e.g., a signature) encrypted with a sender""s private key corresponding to the sender""s public key.
An asymmetric algorithm assumes that public keys are well publicized in an integrity-secure manner. A sender (user of a public key associated with a receiver) can then know that the public key is valid, effective, and untampered with. One way to ensure integrity of data packets is to run data through a cryptographic algorithm. A cryptographic hash algorithm may encrypt and compress selected data. Such hash algorithms are commercially available. For example, the message digest 5 (MD 5), and the message digest 4 (MD 4) are commercially available software packages or applications for such functions.
A certificate may be thought of as a data structure containing information or data representing information, associated with assurance of integrity and/or privacy of encrypted data. A certificate binds an identity of a holder to a public key of that holder, and may be signed by a certifying authority. A signature is sometimes spoken of as binding an identity of a holder to a public key in a certificate. As a practical matter, a certificate may be very valuable in determining some level of confidence in keys associated with encryption. That is, just how xe2x80x9cgoodxe2x80x9d is an encryption in terms of privacy and integrity? That confidence level may be established by means of a certificate hierarchy. By certificate hierarchy is meant a certification process or series of processes for providing certificates from a trusted authority to another creator of keys.
A certificate, being a data structure, may contain, for example, data regarding the identity of the entity being certified as the holder of the key associated with the certificate, the key held (typically it is a public key), the identity (typically self-authenticating) of the certifying authority issuing the certificate to the holder, and a digital signature, protecting the integrity of the contents of the certificate. A digital signature may typically be based on the private key of the certifying authority issuing the certificate to the holder. Thus, any entity to whom the certificate is asserted may verify the signature corresponding to the private key of the certifying authority.
In general, a signature of a certifying authority is a digital signature. The digital signature associated with a certificate enables a holder of the certificate, and one to whom the certificate is asserted as authority of the holder, to use the signature of the certifying authority to verify that the contents of the certificate have not been modified. Such verification assures the integrity and authenticity of the certificate and of the public key in the certificate. This verification is accomplished using the certifying authority""s public key.
Government authorities throughout the world have interests in controlling the use of cryptographic algorithms and keys. Many nations have specific policies directed to creation, use, import, and export of cryptographic devices and software. Numerous policies may exist within a single government. Moreover, these policies are undergoing constant change periodically.
Cryptographic policies may limit markets. For example, a cryptographic algorithm may not be included in software shipped to a country having laws restricting its importation. On the other hand, such a cryptographic device may be desired, highly marketable, and demanded by the market in another country. Thus, generalized software development, standardization of software, and the like may become difficult for software vendors. Moreover, users have difficulties attendant with supporting limited installed bases of specialized software. That is, a sufficient installed base is required to assure adequate software.
In short, cryptographic use policies sometimes constrain the set of cryptographic algorithms that may be used in a software system. In addition to restrictions on allowable algorithms, cryptographic use policies may also place constraints on the use and strength of keys associated with those algorithms. Software shipped or used in any country must be in compliance with the extant policies.
Another common aspect of certain cryptographic use policies is a requirement that a copy of cryptographic keys be stored or xe2x80x9cescrowedxe2x80x9d with an appropriate authority. However, the mechanisms necessary to satisfy different policies can vary greatly.
Cryptography, especially public key cryptography, provides certain benefits to software designers. U.S. Pat. No. 4,200,700, U.S. Pat. No. 4,218,582, and U.S. Pat. No. 4,405,829 are directed to such technology and are incorporated herein by reference. These benefits are available in situations where data may be shared. Many modern software packages (applications, operating systems, executables) are used in businesses or in other networks where multiple xe2x80x9cclientsxe2x80x9d may share a network, data, applications, and the like. Most modem software packages employ cryptography in some form.
One application for cryptography in network management or network operating systems includes authentication. Also, integrity of data packets transferred, encryption of files, encoding associated with licenses for software or servers, and license distribution or serving are some of the applications for cryptography.
Users may be identified and their rights to access may be authenticated by means of passwords on a network. Cryptography is typically used to transfer some authentication, integrity, verification, or the like in a secure manner across a network that may be open to channel tapping. Public key cryptography is typically used in such a circumstance. Another application of cryptography for authentication involves a single sign-on. For example, a user may need to enter a single password at the beginning of a session. This may remain true regardless of the number of servers that may eventually be called into service by the individual user (client) during this single session. Historically, scripts have been used to provide a single sign-on, but public key mechanisms are now being provided for this function.
Users have previously demonstrated that networks may be subject to attack by spoofing of network control packets. This procedure may be demonstrated in playback and in man-in-the-middle scenarios. By such spoofing, users may obtain unauthorized privileges on a network server. Adding packet signatures, keyed on a per-session basis may provide improved packet integrity.
File encryption is becoming more available. Such encryption has particular use in the special circumstance of audit files. For example, a need exists to protect an audit trail from inspection or modification, or both, by a system administrator, even though the audit trail remains under the system administrator""s physical control.
Certain licensing schemes may use various encryption modes to protect software against piracy by end users and others throughout a distribution chain. Data structures, cryptography methodologies, checks, and other protection mechanisms may be proprietary to a software developer. Nevertheless, license server mechanisms are being developed to support control of the use of application software in conformity with licenses. Licenses may be provided by an application software provider. The license server may use public key cryptography to create and verify signed data structures. Secret key cryptography may be used to support authentication and file encryption.
Certain applications may provide file confidentiality using proprietary, exportable, secret key algorithms. Users in large numbers make use of such algorithms. Nevertheless, considerable interest in breaking such proprietary algorithms has been successful with certain software. Proprietary encryption methodologies have been consistently broken, given enough time and attention by interested hackers.
Certain applications use public key cryptography for digital signatures. Market leaders in software have provided relatively weak secret key algorithms adopted by others. Thus, files written in different applications from different vendors, even encrypted files, may be opened by an application from any of the vendors using the market leader""s secret key algorithm. Within a single product line, a vendor of software applications may use multiple algorithms. Several, if not a plethora of, algorithms exist, including both secret key algorithms and public key algorithms. Stream and block ciphers, as well as hash functions are available and well documented in the computer programming art. Also, certain algorithms are the subject of patent applications which may cloud their broadly based use.
What is needed is a standardized cryptography methodology for distribution across entire product lines. Moreover, encryption technologies are needed for permitting a licensee of a principal software manufacturer to become a third party vendor or value-added distributor capable of producing its own proprietary software, software additions, or pre-planned software modules. Currently, software-with-a-hole may provide an operating system with a cryptographic module that fits in the xe2x80x9cholexe2x80x9d in an operating system. However, software manufacturers using this technology typically require that a third-party vendor send its product to the principal software manufacturer for integration. The manufacturer may then provide all interfacing and wrapping of the third-party""s filler (such as an encryption engine) to fit within the xe2x80x9cholexe2x80x9d in the software of the manufacturer.
Also, export restrictions exist for encryption technology. Limiting the strength of exported cryptography is established by statute. To be exportable, such products must meet certain criteria (primarily limitations on key size) that effectively prevent the exportation of strong cryptographic mechanisms usable for data confidentiality. Moreover, creating xe2x80x9ccryptography with a holexe2x80x9d is undesirable for several reasons, including export and import restrictions. Cryptography with a hole is the presence of components specifically designed or modified to allow introduction of arbitrary cryptographic mechanisms by end users. A great escalation of the difficulty of such introduction, without creating numerous, individually customized software packages, is a major need today, although not necessarily well-recognized.
Certain foreign countries have more stringent regulation of the importation of encryption technology by non-government entities. A government may require that any imported encryption technology be subject to certain governmental policies as well as key escrow by some governmental agency. Key escrow systems may be easily provided in software, but integrity and assurance remain difficult. Using only software, reliable key escrow may be impossible, in the absence of very high assurance. For example, Class B3 or A1 may be required of a xe2x80x9ctrusted computing basexe2x80x9d in order to protect keys against disclosure or modification. Likewise, protection of algorithms against disclosure or modification, and escrow against bypass, are also often required. Under any circumstances, software offers few protections when compared with hardware solutions.
Customers, whether third-party vendors, distributors, or end users, need information security. International commercial markets need products that may be marketed internationally without a host of special revisions that must be tracked, updated, and maintained with forward and backward compatibility as to upgrades and the like. Meanwhile, such solutions as key escrow do not receive ready customer acceptance in U.S. markets, particularly where a government is an escrow agent.
Flexibility of encryption technologies is also important, particularly to software development. For instance, it is important that standards or properties be created for managing access to encryption technologies. At the same time, it is likely that the properties will change over time, and the properties should be easily modified. The properties should also be securely contained with specific applications implementing the encryption technologies.
Personal computers, including laptops, workstations and other more powerful computers, are increasingly linked through communications networks, the span and scope of which are increasing daily. Whereas once computers were only accessed and used within the secure confines of glass-enclosed computer rooms, today they are often accessed remotely, even from the other side of the world. Likewise, although in the past company-owned communications facilities, dedicated private networks, and/or value-added Networks provided a certain amount of control over who could connect to them, today public facilities such as the Internet are very widely used to provide ubiquitous interconnection.
But with the new ubiquitous communications paradigm comes an almost equally ubiquitous concern about the privacy, security, and integrity of the data that is being transmitted and received. In addition to eavesdroppers potentially gaining access to proprietary or personal information, we also have to worry about virus and Trojan Horse programs maliciously modifying data, allowing unauthorized users to access sensitive control functions, or even destroying massive amounts of data and thereby threatening the very survival of the organization, including our sensitive public infrastructure.
Thus, it becomes of concern in systems in which independent entities share resources and otherwise intercommunicate, that the independent entities may never be sure about the origin or integrity of the other entities with which they are communicating. This concern is particularly acute with respect to underlying base applications such as entities that are the providers of an underlying operating system or infrastructure.
There are a number of reasons why it would be desirable for an application to authenticate a base entity. One reason is just for the sake of assuring the correct functioning of the application. For example, mission-critical software applications are written independently of the operation systems used to support them, yet the developers of such need to verify that the operating system has not been modified in order to assure the correct functionality of the application.
Another potential application for authentication of a base entity by an application is in the area of software licensing. Applications may be sold under the condition that a single copy of the application be run on only one particular platform, and not multiple platforms or on network servers. In order to enforce this provision, the application needs to be able to authenticate the particular version of the operating system it is running on.
The most generally applicable solution to this entire broad class of problems is the use of cryptography, which can prevent anyone not in possession of both the cryptographic algorithm and the necessary cryptographic key from being able to read anything but gibberish from the communications, and in the case of cryptographic algorithms used to provide digital signatures and authentication, from being able to modify or delete the information without detection.
Nevertheless, the use of cryptography has its darker side. Traditionally because of its association with the military and the diplomatic corps, the use of cryptography has long been regarded as the exclusive province of governments, and some countries have even prohibited its use without specific permission.
In addition, the use of cryptography by criminal elements has always been a potential threat, and the recent increase in and/or sensitivity to drug related crimes, money laundering, and the potential use by terrorist organizations has significantly increased the concern within various governments as to the possibility of misuse of cryptography.
During the Cold War period, the export of cryptography from the United States was a primary concern, as the U.S. did not want our adversaries to gain access to effective cryptography which our intelligence agencies could not break. The export of cryptographic products, including the technical data describing them, was forbidden under the International Traffic in Arms Regulations, except under licence from the U.S. Department of State. The use of cryptography by U.S. citizens within the United States (or by the Canadians, who implemented an export regime which was the virtual duplicate of that administered by the U.S.) was not considered a significant concern, however.
Unlike other countries with a tradition of an Official Secrets act, such as the UK, or a somewhat more repressive xe2x80x9conly that which is explicitly allowed is not forbiddenxe2x80x9d policy, the U.S. does not have any legal barriers which would prevent its citizens from making use of whatever kind of cryptography they would like to use. However, the use of unbreakable encryption mechanisms causes considerable anxiety within some of the law enforcement agencies, for they fear that their ability to investigate and prosecute criminals and terrorists, both inside and outside of our borders, may be severely hampered by the unfettered use of encryption by the general populous, including the criminal and terrorist elements.
Because of the importance of cryptography in protecting our business assets and enabling electronic commerce, the law enforcement agencies are not necessarily opposed to the use of cryptograph per se, but they do seek ways of controlling its use and/or providing mechanisms which would allow authorized access to the secret encryption keys, including covert and near-real-time access to such keys in order to facilitate investigations.
Because Congress has so far not seen fit to pass legislation which would either directly control the uses of encryption within the U.S., or would officially grant the law enforcement agencies the right to access the encryption keys that are used, the Administration has reportedly decided to use the existing export regulations to put pressure on hardware and software vendors who would like to export their products worldwide, in particular requiring them to include so-called key escrow, or key recovery mechanisms in their products in order to obtain an export license for anything better than weak (e.g., 56-bit) encryption.
However, one of the technical concerns that the export authorities have in this regard is the possibility that users of export-controlled software (including software which invokes export-controlled software or hardware) should not be able to defeat the key recovery and other controls by substituting other, non-controlled software which would provide the same functionality but with stronger cryptography and/or without key recovery. Although the specific cryptographic algorithms are widely published and readily available, the infrastructure necessary to actually use those cryptographic algorithms, including the integration into commercial software, is not nearly so easy accessed. This concern is frequently referred to as the xe2x80x9cCrypto-with-A-Holexe2x80x9d problem.
Applications which directly include cryptographic functionality within their executable (binary) modules generally do not evince this level of concern, because the modules are statically bound together, and replacing the cryptographic functionality with something else would typically require a substantial amount of reverse engineering. However, directly incorporating the necessary cryptographic functionality into every application is very wasteful of the engineering talent required to write such systems, and leads to substantially greater software maintenance costs as well, in addition to being wasteful of the excess storage required. Instead, it would be highly desirable if a general purpose cryptographic infrastructure could be deployed which could be called by whatever applications required the functionality. The cryptography would therefore be integrated into the operating system, or provided as a common adjunct to the operating system which other programs could use.
Not only would this greatly simplify the development of such applications, but if it could be demonstrated that the applications only made use of those cryptographic functions and keys which were considered relatively safe or benign (e.g., digital signatures and keys used for authentication or nonrepudiation, as opposed to encryption without key recovery), then export would likely be possible and an expedited export review process might be possible, resulting in a significantly decreased time to market for application developers, and reduced legal expenses as well.
However, the key to the development of a common cryptographic infrastructure is the use of dynamic linking mechanisms which are resolved by the loader, or at run-time (by name), rather than using static linkages. And unfortunately, the use of such dynamic linkage mechanisms (e.g., the Dynamic Link Library or DLL calls typically used in many operating systems) would vastly simplify the substitution of one kind of an uncontrolled cryptographic infrastructure in place of a controlled and export-approved infrastructure, thereby giving rise to a substantial threat of a crypto-with-a-hole.
In this environment, however, it is assumed that the commercial software which makes use of the cryptographic infrastructure is relatively benign, for if it could be shown that the application was designed in such a way as to facilitate such a substitution without substantial effort, the application developer would presumably be in violation of the export laws if they shipped such a product outside of the U.S. or Canada, or if they imported or used it in violation of the laws of those countries which prohibit it.
Therefore, if the application which invokes the cryptographic function were able to authenticate the cryptographic infrastructure prior to invoking it, and perhaps later during a series of ongoing invocations as well, in order to reasonably prevent the unauthorized substitution of a different set of capability after the initial authentication, then a reasonable level of assurance could be provided to the export authorities that although the application makes use of cryptography, it does not contain it, and in addition contains mechanisms to ensure that only the approved cryptographic infrastructure is invoked without the possibility of substitution, the application does not give rise to a crypto-with-a-hole problem. The applications would then presumably deserve an expedited export review process, or ideally no export license would be required at all.
Unfortunately, there are certainly obvious difficulties in implementing such an authentication mechanism, not the least of which is that the only effective way to authenticate an application is through the use of cryptography, and it is the use of cryptography that we are trying to authenticate! This apparently circular reasoning requires very careful controls on exactly what kinds of cryptography is used to do the authentication, and where and how it is implemented, in order not to violate the basic controls that are to be enforced.
Accordingly, a need exists for a system through which two independent, resource sharing, executable entities may authenticate the identity, origin, and continuing integrity of the other.
Such a system is likewise needed whereby an application entity may access the resources of an underlying base entity (such as an operating system) in a manner by which it can be assured that the resources being shared are authorized and in compliance with government and vendor policies.
Such a system is similarly needed whereby counterpart components of the system may be flexibly distributed into standard authenticating modules and authenticated modules which are capable of inclusion into applications entities and base entities, respectively, and which can be statically linked in a trustworthy manner within those entities, while being dynamically linkable to each other.
The apparatus of the present invention has been developed in response to the present state of the art, and in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available technology. Thus, it is an overall objective of the present invention to provide a system and method whereby independent, resource sharing, executable entities can unilaterally or bilaterally authenticate other such entities prior to the sharing of resources between the entities.
Consistent with the foregoing object, and in accordance with the invention as embodied and broadly described herein, an apparatus and method are disclosed in certain embodiments of the present invention as including a method and apparatus for effecting secure communications between independent, resource sharing, executable entities.
In order to effect the secure communications, the present invention initially authenticates unknown executable entities to each other, either unilaterally or bilaterally. As a further feature of the present invention, an enduring authentication state may be maintained, and may make minimal use of cryptography in the executable entity which seeks to authenticate the other.
In an instance wherein an application executable entity (e.g., a software program) wishes to authenticate a base executable entity (e.g., a network operating system), the process includes sending a challenge nonce from the application to the base executable entity. The base executable entity digitally signs the challenge nonce. The base executable returns to the application the signed challenge nonce and its own generated nonce as a pair of variables. The application executable entity unwraps the signed challenge nonce with a public key to authenticate the base executable. The application also authenticates the base executable""s nonce, decrypting it, if required, and using it in ongoing authentication of subsequent calls or messages to the base executable.
The dynamic authentication system and method may also require that the application executable entity authenticate the base executable entity with a chain of asymmetric key pairs, the public keys of which may be embedded in digitally signed certificates. In one embodiment, the public key pairs include a run-time-generated public key pair, a per-instance (e.g., release-time, or distribution time) public key pair, and a certifying authority master or root key pair.
The chain of digitally signed keys that is used in the authentication process may be in a standard certificate format such as that specified by X.509 or in a proprietary format. The chain of signed keys may include a run-time key which is generated at application start-up on a per-context basis; a distribution-time key which is unique per server and is generated at either install time or at customer order time; a per-release key which is generated by the vendor at the time of release of a particular version and/or for a particular customer set, country, or region; and the top-level or root, a vendor-master key, which has a relatively long life span. In general, a list of one or more root or top-level public authentication keys may be securely embedded in the application entity in such a way as to make difficult replacement without substantial reverse engineering. The chains of certificates corresponding to each root may contain certificate attributes reflecting properties of certificates such as the quality of the confidentiality protection for the private key, the cryptographic process quality for creation of the certificate, and the identity of the enterprise creating any certificate in the chain. Thus quality attributes may be used as constraints on authentication of a base executable.
The use of a run-time key plus a distribution-time key and a per-release key adds a dimension of both space and time variability to ensure that a compromise of one of the keys is not sufficient to defeat the entire system. The inclusion of a standard distinguished name or other identification information (such as a license number) in the distribution-time key certificate may readily identify anyone attempting to distribute a valid distribution-time private key and certificate to other unauthorized users. Standard certificate revocation list technology or a certificate registry may then be used to revoke any misused certificates. The use of a short-lived run-time key permits the use of short public-key encryption keys, which in turn facilitates the periodic re-authentication of the state of the two applications. The two applications may be either statically or dynamically loaded on the same computing system, e.g., as part of an operating system which is called by an invoking program, or they may be separated and communicate via an arbitrary communications link and protocol.
Once the identity, origin, and integrity of the base executable entity has been authenticated by the application entity using the challenge and response and the chain of asymmetric key pairs, a signed state variable (e.g., the base executable""s nonce) is preferably used to maintain an on-going state synchronization between the base and the privileged utility set in the application, and continue the authentication across multiple function calls.
The state variable can be made a function of the number of calls and the contents of all of the arguments which are passed back and forth between the application entity and the base entity, and is updated by both the application entity and the base entity after every call. For example, simple incrementation of the nonce by the base executable and the application may suffice, Alternatively, the use of a secure hashing function such as SHA-1, for example, may improve security. The state variable can then be used to modify the interface between the two applications, e.g., by adding or Exclusive Or-ing (X-ORing) the variable with the address of the parameter list(s) being passed back and forth, so that if the state variables are not synchronized between the two applications, the function calls will fail to work properly.
Accordingly, if an interloper attempts to replace the base entity after the initial authentication, he/she will not know the correct state information unless he/she has been monitoring all of the communications in both directions since the state information was last authenticated. Encrypting the base executable nonce and its updated values may be employed to resist this type of attack from interlopers.
To further protect against the possibility of this kind of a man-in-the-middle attack, the authenticating application can issue a new challenge as often as necessary, for example when changing context or prior to any critical operation. Since the challenge is taking place in real-time, a short private key can be used for the run-time key used to sign the challenge, so the operation will take a minimal amount of time. In addition, since the run-time key and per-instance key have been previously validated, that step of the process will not have to be repeated.
These and other objects, features, and advantages of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.